During the past years, various business models envision the use of large-scale distributed systems. These systems are hard to deploy and have their own challenges. One such example is distributed hash tables (DHTs). To lower the barriers facing DHT-based applications, a public DHT service called OpenDHT has been created (see for example, Rhea et al., OpenDHT: A Public DHT Service and Its Uses, Proceedings of the ACM SIGCOMM Conference on Computer Communications, 2005, the entire content of which is incorporated herein by reference).
REsource LOcation And Discovery (RELOAD) is a Peer-to-Peer (P2P) signaling protocol that can be used to maintain the overlay network and to store data in and retrieve data from the overlay. In a P2P overlay network such as a RELOAD Overlay Instance, the peers forming the overlay share their resources in order to provide the service the system has been designed to provide. The peers in the overlay both provide services to other peers and request services from other peers. Examples of possible services offered by peers in a RELOAD Overlay Instance include a TURN relay service, a voice mail service, a gateway location service, and a transcoding service. Typically, only a small subset of the peers participating in the system are providers (service providers) of a given service. A peer that wishes to use a particular service (service client) faces the problem of finding peers that are providing that service from the Overlay Instance.
Although RELOAD defines a Traversal Using Relays around Network Address Translation (TURN) specific service discovery mechanism, it does not define a generic service discovery mechanism as part of the base protocol. A Recursive Distributed Rendezvous (ReDiR) service discovery mechanism used in the OpenDHT discussed above can be applied to RELOAD overlays.
ReDiR is a service discovery mechanism for structured P2P overlay networks. As noted above, ReDiR has been adopted as a service discovery mechanism for the RELOAD protocol that is being specified in the Peer-to-Peer Session Initiation Protocol (P2PSIP) working group of the Internet Engineering Task Force (IETF). The RELOAD protocol and thus also ReDiR are used to enable the P2PSIP distributed interpersonal communication service.
ReDiR implements service discovery by building a tree structure of the peers that provide a particular service. ReDiR trees are service-specific, i.e., each service has its own ReDiR tree. The tree structure is embedded tree node by tree node into a DHT based P2P overlay network using the regular “Put” and “Get” requests provided by the DHT. The purpose of a Put request is to store a data record into the P2P overlay network, whereas the purpose of a Get request is to fetch a data record from the network.
Each tree node in the ReDiR tree contains pointers to peers providing a particular service. The ReDiR tree 10 is illustrated in FIG. 1. The tree 10 has multiple levels 12 to 18. Each tree node belongs to a particular level. For example, tree nodes 24a-d belong to level 16. The root 12 of the tree 10 contains a single node 20 at level 0. The immediate children of the root are at level 1, and so forth. The ReDiR tree has a branching factor b, which is 2 in the example shown in FIG. 1. At every level “i” in the tree, there are at most b′ nodes. The nodes at any level are labeled from left to right, such that a pair (i, j) uniquely identifies the jth node (counted from the left) at level i. The tree is embedded into the DHT node by node, by storing the values of node (i, j) at key H(namespace, i, j), where H is a hash function such as Secure Hash Algorithm One (SHA-1), and namespace is a string that identifies the service being provided. As an example, the namespace of a TURN relay service could be for instance the string “turn-service”.
Each level in the ReDiR tree spans the whole identifier space 28 of the DHT. At each level, the ID space is divided among the tree nodes. Each tree node is further divided into b intervals. In FIG. 1, each tree node has two intervals because b=2. As an example, because level 2 in the figure has 4 tree nodes, each of which has two intervals, the whole identifier space of the DHT is at that level divided into 8 parts (i.e., intervals). When storing a record with identifier X in a given level, the record is stored in the interval within whose range X falls.
The act of storing a record in the ReDiR tree is referred to as ReDiR service registration procedure. The act of fetching a record from the ReDiR tree is referred to as ReDiR service discovery operation. It is noted that the ReDiR and RELOAD protocols are known in the art and they are standardized and it is not obvious for one skilled in the art to modify these protocols.
Various simulations run for the ReDiR protocol have identified a number of areas where ReDiR performs poorly. One finding is that ReDiR does not distribute the service clients equally among the service providers. Another issue is that ReDiR does not take into account the heterogeneity of service providers as ReDiR assumes that all the service providers have equal capacity.
Accordingly, it would be desirable to provide devices, systems and methods that avoid the afore-described problems and drawbacks.